package argo.hot100.graph;

public class Trie {

    class
    Node {
        Node[] children;
        boolean isEnd;

        Node() {
            children = new Node[26];
            isEnd = false;
        }
    }

    Node node;

    public Trie() {
        node = new Node();
    }

    public void insert(String word) {
        Node cur = node;
        for (char c : word.toCharArray()) {
            int inx = c - 'a';
            if (cur.children[inx] == null) {
                cur.children[inx] = new Node();
            }
            cur = cur.children[inx];
        }
        cur.isEnd = true;
    }

    public boolean search(String word) {
        Node node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        Node node = searchPrefix(prefix);
        return node != null;
    }

    public Node searchPrefix(String word) {

        Node cur = node;
        for (char c : word.toCharArray()) {
            int inx = c - 'a';
            if (cur.children[inx] != null) {
                cur = cur.children[inx];
            } else {
                return null;
            }
        }
        return cur;
    }
}
